package dp;

//最小矩阵和 问题
//给定一个矩阵  从左上角开始每次只能向下或者向右走  最后到达右下角位置  路径上所有数字累加起来就是路径和   返回所有路径和中最小的路径和
/*
* 例如：
* 1 3 5 9
* 8 1 3 4
* 5 0 6 1
* 8 8 4 0   最小路径为1 3 1 0 6 1 0 最小路径和为12   矩阵用等行等列的二维数组表示
* */
public class MinSumJunZhen {
    public static void main(String[] args) {
        int[][] arrs = {
                {1,3,5,9},
                {8,1,3,4},
                {5,0,6,1},
                {8,8,4,0}};
        System.out.println("最终结果"+getMinWithDp(arrs,6));

    }
    //先使用暴力递归   a和b代表横纵坐标  初始为目的地的坐标
    public static int getMinSum(int[][] arrs,int a,int b){
         if (a==0 && b==0){
             System.out.println(arrs[a][b]);
             return arrs[a][b];
         }
         if ((a<0 || b<0)){
             return 100;
         }
         //右和下 和 较小的路径
        int res = Math.min(getMinSum(arrs,a-1,b),getMinSum(arrs,a,b-1))+arrs[a][b];
        System.out.println(res);
         return res;
    }

    //改动态规划 使用一维数组进行空间压缩   k代表总步数
    public static int getMinWithDp(int[][] arrs,int k){
        int i=0,j=0;
        int[] res = new int[k];
        res[k-1] = arrs[3][3];
        for (int a=k-2;a>=0;a--){
            res[a] = res[a+1] +  (arrs[i+1][j] <arrs[i][j+1] ? arrs[++i][j] : arrs[i][++j]);
        }
        return res[0];
    }

}
